#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
#include<string>
#include<vector>
using namespace std;

int find_Max(vector<int>& v){
	int max = v[0];
	int i = 0;
	int max_i = 0;
	while (i<v.size()){
		if (v[i]>max){
			max_i = i;
			max = v[i];
		}
		i++;
	}
	return max_i;
}

bool IsPalindrome(string& s, int begin, int end){
	while (begin<end){
		if (s[begin] != s[end]){
			return false;
		}
		begin++;
		end--;
	}
	return true;
}

class Solution {
public:
	string longestPalindrome(string s) {
		int left = 0;
		int right = s.size();
		vector<int> v(s.size(), 0);
		while (left<s.size()){
			right = s.size();
			while (right>left){
				while (right>left&&s[left] != s[right]){
					right--;
				}

				if (IsPalindrome(s, left, right)){
					v[left] = right - left;
					break;
				}
				right--;
			}


			left++;
		}

		int max = find_Max(v);

		return string(s, max, v[max] + 1);
	}
};